/*
 * @lc app=leetcode.cn id=327 lang=golang
 *
 * [327] 区间和的个数
 */

// @lc code=start
func countRangeSum(nums []int, lower int, upper int) int {
	// 前缀和数组，第0位为0，占位，方便计算前缀和的差
	arrSum := make([]int, len(nums)+1)
	sum := 0
	ans = 0
	up = upper
	low = lower
	// 初始化前缀和数组
	for index, val := range nums {
		sum += val
		arrSum[index+1] = sum
	}
	// 归并排序
	mergeSort(arrSum, 0, len(arrSum)-1)
	return ans
}

var ans int
var up int
var low int

func mergeSort(arr []int, left, right int) {
	if left >= right {
		return
	}
	mid := (left + right) / 2
	mergeSort(arr, left, mid)
	mergeSort(arr, mid+1, right)
	caculate(arr, left, mid, right)
	merge(arr, left, mid, right)
}

// 计算区间个数
func caculate(arr []int, left, mid, right int) {
	i := left
	j := mid + 1
	k := mid + 1

	for i <= mid {
		for j <= right && arr[j]-arr[i] < low {
			j++
		}

		for k <= right && arr[k]-arr[i] <= up {
			k++
		}
		//fmt.Println(k," ",j)
		ans += k - j
		i++
	}
}

// 合并数组
func merge(arr []int, left, mid, right int) {
	temp := make([]int, right-left+1)
	i := left
	j := mid + 1

	for k := 0; k < len(temp); k++ {
		if j > right || (i <= mid && arr[i] <= arr[j]) {
			temp[k] = arr[i]
			i++
		} else {
			temp[k] = arr[j]
			j++
		}
	}

	for k := 0; k < len(temp); k++ {
		arr[left+k] = temp[k]
	}
}

// @lc code=end

